package 纯数组;

import com.alibaba.fastjson.JSON;

import java.util.*;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-09
 **/

public class No218天际线问题 {

    /**
     * 城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。
     * 给你所有建筑物的位置和高度，请返回由这些建筑物形成的 天际线 。
     * 每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings[i] = [lefti, righti, heighti] 表示：
     * lefti 是第 i 座建筑物左边缘的 x 坐标。
     * righti 是第 i 座建筑物右边缘的 x 坐标。
     * heighti 是第 i 座建筑物的高度。
     * 天际线 应该表示为由 “关键点” 组成的列表，格式 [[x1,y1],[x2,y2],...] ，
     * 并按 x 坐标 进行 排序 。关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点，
     * y 坐标始终为 0 ，仅用于标记天际线的终点。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。
     * 注意：输出天际线中不得有连续的相同高度的水平线。例如 [...[2 3], [4 5], [7 5], [11 5], [12 7]...]
     * 是不正确的答案；三条高度为 5 的线应该在最终输出中合并为一个：[...[2 3], [4 5], [12 7], ...]
     *
     * 示例 1：
     * 输入：buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
     * 输出：[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
     * 解释：
     * 图 A 显示输入的所有建筑物的位置和高度，
     * 图 B 显示由这些建筑物形成的天际线。图 B 中的红点表示输出列表中的关键点。
     * 示例 2：
     * 输入：buildings = [[0,2,3],[2,5,3]]
     * 输出：[[0,3],[5,0]]
     *  
     * 提示：
     * 1 <= buildings.length <= 104
     * 0 <= lefti < righti <= 231 - 1
     * 1 <= heighti <= 231 - 1
     * buildings 按 lefti 非递减排序
     */

    public List<List<Integer>> getSkyline(int[][] buildings) {

        List<List<Integer>> result = new ArrayList<>();
        // 每个点的x,y
        List<int[]> list = new ArrayList<>(buildings.length * 2);

        for (int[] building : buildings) {
            int left = building[0];
            int right = building[1];
            int height = building[2];
            list.add(new int[]{left, height});
            list.add(new int[]{right, -height});
        }

        Collections.sort(list, (o1, o2) -> {
            if (o1[0] == o2 [0]) {
                // x相等,则左端点在前;   大于0,则o1在前
                return o1[1] > o2[1] ? -1 : 1;
            }
            // 大于0,小的在前
            return o1[0] - o2[0];
        });

        Map<Integer,Integer> map = new HashMap<>();
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((i1, i2) -> i2 - i1);
        // 加0的原因是需要取最后一个点,最后一个点需要参照高0
        priorityQueue.add(0);
        map.put(0, 1);
        int preHeight = 0;

        for (int[] ints : list) {
            int x = ints[0];
            int h = ints[1];
            if (h > 0) {
                // 左端点
                priorityQueue.add(h);
                map.put(h, map.getOrDefault(h, 0) + 1);
            } else {
                // 右端点,使用延时删除
//                priorityQueue.remove(-h);
                map.put(-h, map.get(-h) - 1);
            }

            while (map.get(priorityQueue.peek()) <= 0) {
                priorityQueue.poll();
            }

            Integer maxHeight = priorityQueue.peek();

            if (maxHeight != preHeight) {
                List<Integer> resultItem = new ArrayList<>(2);
                resultItem.add(x);
                resultItem.add(maxHeight);
                result.add(resultItem);
                // 一定要记录上次的结果高
                preHeight = maxHeight;
            }

        }

        return result;
    }

    public static void main(String[] args) {
        No218天际线问题 n = new No218天际线问题();
        int[][] arr = {{0,2,3},{2,5,3}};
        List<List<Integer>> result = n.getSkyline(arr);
        System.out.println(JSON.toJSONString(result));
    }

}
